package g

/*
 * @lc app=leetcode.cn id=25 lang=golang
 *
 * [25] K 个一组翻转链表
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？
*/

// ListNode Definition for singly-linked list.
type ListNode struct {
	Val  int
	Next *ListNode
}

// @lc code=start
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
	// return reverseKGroup1(head, k)
	return reverseKGroup2(head, k)
}

// reverseKGroup1 空间复杂度为 o(k) 的算法
func reverseKGroup1(head *ListNode, k int) *ListNode {
	ret := &ListNode{Next: head}
	var kNodes []*ListNode
	head = ret // head指向 k 组数据的上个节点
	p := head.Next
	for p != nil {
		kNodes = append(kNodes, p)
		p = p.Next
		if len(kNodes) == k { //process k node
			head.Next = kNodes[len(kNodes)-1]
			kNodes[0].Next = kNodes[len(kNodes)-1].Next
			head = kNodes[0]
			for i := len(kNodes) - 1; i > 0; i-- {
				kNodes[i].Next = kNodes[i-1]
			}
			kNodes = kNodes[:0]
		}
	}
	return ret.Next
}

// reverseKGroup2 空间复杂度为 o(1) 的算法
func reverseKGroup2(head *ListNode, k int) *ListNode {
	if k <= 1 || head == nil {
		return head
	}
	ret := &ListNode{Next: head}
	head = ret // head指向 k 组数据的上个节点
	for head.Next != nil {
		srcHead := head
		head = swap(head, k)
		if head == nil { //还原
			head = swap(srcHead, k)
			break
		}
	}
	return ret.Next
}

// swap 返回 k 个 Node 排序后最后一个节点，如果不够 k 个，返回nil
func swap(head *ListNode, k int) *ListNode {
	kSrcFirstNode := head.Next // 指向 k 组排序前第一个元素，排序后最后一个元素
	p := kSrcFirstNode         // p、q 指向 k 中的前后两个节点，交换 k 组中的二个 Node
	q := p.Next
	i := 1
	for ; i < k && p != nil && q != nil; i++ {
		head.Next = q
		kSrcFirstNode.Next = q.Next
		q.Next = p
		p = q
		q = kSrcFirstNode.Next
	}
	if i != k { //不够k个的话，返回nil，需要还原替换操作
		return nil
	}
	return kSrcFirstNode
}

// @lc code=end
